#include<vector>
#include<algorithm>
class Solution {
public:
    std::vector<std::pair<int,int>> mid;
    std::vector<int> road ;
    std::vector<std::vector<int>> res ;
    int len = 0;
    std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
        std::sort(nums.begin(),nums.end());
        int last = nums[0];
        int count = 0;
        int index = 0;
        for (int num : nums)
        {
            if (num !=last)
            { mid.push_back({last,count});
                index++;
                last = num;
                count=0;
            }
                count++;
        }
        mid.push_back({last,count});
        len = mid.size();
      
        cal(0);
        return res;
    }
    void cal (int index)
    {
         if (index == len)
        {
             if (road.empty())
             {
                 res.push_back({});
             }else
             {
                 res.push_back(road);
             }
            return;
        }
        for (int i = 0;i<=mid[index].second;i++)
        {
            for (int j= 0;j<i;j++)
            {
                road.push_back(mid[index].first);
            }
            cal(index+1);
            for (int j= 0;j<i;j++)
            {
                road.pop_back();
            }
        }
       
    }
};
